package com.xinwei.leetcode.数组;

import java.util.ArrayList;
import java.util.List;

public class _119_杨辉三角2 {
    public List<Integer> getRow(int rowIndex) {
        // 官方递推方法，和118思路一致，但更巧妙简洁
        List<List<Integer>> C = new ArrayList<List<Integer>>();
        for (int i = 0; i <= rowIndex; ++i) {
            List<Integer> row = new ArrayList<Integer>();
            for (int j = 0; j <= i; ++j) {
                if (j == 0 || j == i) {
                    row.add(1);
                } else {
                    row.add(C.get(i - 1).get(j - 1) + C.get(i - 1).get(j));
                }
            }
            C.add(row);
        }
        return C.get(rowIndex);
    }

    // 注意到在递推的方法中对第i+1行的计算仅用到了第i行，所以用滚动数组进行优化，滚动数组可以优化空间复杂度
    public List<Integer> getRow1(int rowIndex) {
        ArrayList<Integer> pre = new ArrayList<>();
        for (int i = 0; i <= rowIndex; i++) {
            ArrayList<Integer> cur = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    cur.add(1);
                } else {
                    cur.add(pre.get(j - 1) + pre.get(j));
                }
            }
            pre = cur;
        }
        return pre;
    }

    /**
     * 进一步优化  只用 1 个数组
     *        1
     *       1 1
     *      1 2 1
     *     1 3 3 1
     *     从 1 2 1 变成 1 3 3 1 需要
     *   给121加一位0，变成1210，让0+1=1，1+2=3，2+1=3（当前位加前一位的值）
     */
    public List<Integer> getRow2(int rowIndex) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        for (int i = 1; i <= rowIndex; i++) {
            list.add(0);
            for (int j = i; j > 0; j--) {
                list.set(j, list.get(j) + list.get(j - 1));
            }
        }
        return list;
    }
}
